There are numerous circumstances in which it is useful to determine if a specified path is blocked by a specified obstacle. For example, in robotics, the system may need to find a clear path through a known terrain to a specified destination. This would apply equally well to a fixed position robot with a moveable arm as to a moveable robot. For instance, the outer boundary of a robot arm can be represented by a set of line segments representing the arm's "wire frame", and for any given arm position or future arm position intersection of any of those line segments with a known object indicates that movement of the robot arm to that position would cause a collision.
Other applications include checking an airplane's proposed trajectory against a known terrain and/or set of obstacles, and hidden ,line calculations for video display systems.
The present invention provides a fast solution to the question: does a given line in space intersect a given volume? Alternately, the invention can be used to generate a representation of the relationship between two points and a given volume, thereby providing data for selecting one of a number of possible subsequent calculations.
Path blockage analysis is usually accomplished using a general purpose a computer programmed to perform a series of mathematical calculations. In U.S. Pat. No. 4,764,873, dedicated hardware is used to analyze the relationship between a path and an obstacle by converting path and obstacle data into a form suitable for fast analysis and then performing a set of comparisons that sort the path into one of three classes: path obstructed (called a Hit), path clear (called a Miss), or path may be blocked (called Ambiguous). If the initial analysis is ambiguous, U.S. Pat. No. 4,764,873 teaches that the two dimensional path blockage problem can be resolved by performing slope comparison computations. However, for three dimensional path checking problems, the amount of computation required to resolve such ambiguities is considerable. In particular, the technique of the '873 patent to resolve ambiguities for a three-dimensional path is to evaluate a set of planes, of which contains an object edge and one of the two path end points. Then the second end point of the path is evaluated with respect to which side of this plane the point is situated. In the worst case, ambiguity resolution requires evaluation of one path point with respect to twelve planes, each evaluation requiring computation of the determinant of a 3.times.3 matrix. The sign of the resulting determinant indicates which side of a given plan the point in question is located. When the point has been evaluated with respect to all twelve planes, an additional set of logical conditions have to be tested in order to detect an intersection.
The present invention improves on U.S. Pat. No. 4,764,873 by providing an apparatus and method for minimizing the number of computations required to resolve three dimensional path blockage determinations that are not resolved by the first stage path analyzer hardware. One aspect of minimizing computations is to use an improved coordinate mapping (or labeling) method that facilitates identification of the minimum number of object planes that need to be checked for intersection by a specified line segment. The number of planes to be checked, using the present invention, in the worst case is three and in many cases the number of planes to be checked is one or two. Also, instead of requiring the computing of determinants, the present invention requires computation of no more than four relatively simple linear equations for each plane to be checked.
Furthermore, the present invention provides hardware implementations that can reduce computation time for even the worst case three dimensional path blockage determinations to something on the order of three microseconds when using a dedicated computational unit with a 40 MegaHertz clock rate and arithmetic circuitry capable of performing multiplications in a single clock cycle.
A very large percentage of paths can be conclusively determined to be a hit or a miss by the first stage hardware, thereby providing a path blockage determination in a time period on the order of four logic circuit gate delays. Using fast logic circuits, and a fully pipelined circuit architecture, the initial stage of path analysis can typically be completed in 50 nanoseconds (i.e., two clock cycles). The average path analysis computation time for a single path analyzer, using a dedicated computational unit to resolve ambiguities, is approximately 0.5 microseconds. By using several (e.g., eight) parallel path analyzer units, the average path analysis computation time can be reduced even further.
It is therefore a primary object of the present invention to provide a path blockage analysis system and method which performs three dimensional path analyses substantially faster than it would take a conventional computer to perform the same analysis.
Another object of the present invention is to provide a path blockage analysis system which simultaneously performs a set of predefined comparisons to determine the relationship between a specified path and a given obstacle.